import java.util.Arrays;

/**
 * 31. 下一个排列
 */
public class Solution_31 {
    /**
     * 官方题解
     * <p>
     * 将一个左边的「较小数」与一个右边的「较大数」交换，以能够让当前排列变大，从而得到下一个排列。
     * <p>
     * 同时要让这个「较小数」尽量靠右，而「较大数」尽可能小。
     * <p>
     * 当交换完成后，「较大数」右边的数需要按照升序重新排列。 
     * 这样可以在保证新排列大于原来排列的情况下，使变大的幅度尽可能小。
     * 
     * @param nums
     */
    public void nextPermutation(int[] nums) {
        // 「从后向前」查找第一个顺序对 (i,i+1)，满足 a[i] < a[i+1]。「较小数」即为 a[i]
        int i = nums.length - 2;
        while (i >= 0 && nums[i] >= nums[i + 1]) {
            i--;
        }

        if (i >= 0) {
            // 如果找到了顺序对，那么在区间 [i+1,n) 中「从后向前」查找第一个元素 j 满足 a[i] < a[j]
            // 「较大数」即为 a[j]
            int j = nums.length - 1;
            while (j >= 0 && nums[i] >= nums[j]) {
                j--;
            }
            // 交换 a[i] 和 a[j]
            swap(nums, i, j);
        }

        // 此时区间 [i+1,n) 必为降序，反转区间 [i+1,n) 使其变为升序
        reverse(nums, i + 1, nums.length - 1);
    }

    /**
     * 交换数组中两个元素
     * 
     * @param nums
     * @param i
     * @param j
     */
    public void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    /**
     * 将数组从 start 到 end 的数字反转
     * 
     * @param nums
     * @param start 开始索引
     * @param end   结束索引（包含）
     */
    public void reverse(int[] nums, int start, int end) {
        while (start < end) {
            swap(nums, start, end);
            start++;
            end--;
        }
    }

    public static void main(String[] args) {
        Solution_31 solution = new Solution_31();
        int[] nums = { 1, 5, 8, 4, 7, 6, 5, 3, 1 };
        solution.nextPermutation(nums);
        System.out.println(Arrays.toString(nums));
    }
}
